/*
  区间乘积
  题目描述
    小杨有一个包含 n 个正整数的序列 A = [a1, a2, … , an]。
    小杨想知道有多少对 ⟨l, r⟩ (1 ≤ l ≤ r ≤ n) 满足 al * a(l+1) * … * ar 为完全平方数。
    一个正整数 x 为完全平方数当且仅当存在一个正整数 y 使得 x = y * y。
  输入格式
    第一行包含一个正整数 n，代表正整数个数。
    第二行包含 n 个正整数 ai，代表序列 A。
  输出格式
    输出一个整数，代表满足要求的 ⟨l, r⟩ 数量。
  样例 1
    输入
      5
      3 2 4 3 2
    输出
      2
    解释
      满足条件的 ⟨l, r⟩ 有 ⟨1, 5⟩ 和 ⟨3, 3⟩。
  数据范围
    子任务   数据点占比     n           ai
      1         20       ≤ 10^5     1 ≤ ai ≤ 2
      2         40       ≤ 100      1 ≤ ai ≤ 30
      3         40       ≤ 10^5     1 ≤ ai ≤ 30
*/